package com.berchen.offer;

import java.util.ArrayList;

/**
 * 输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。
 * 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
 * 2.叶子节点是指没有子节点的节点
 * 3.路径只能从父节点到子节点，不能从子节点到父节点
 * 4.总节点数目为n
 */
public class Test06 {

    public static void main(String[] args) {
        TreeNode root=new TreeNode(10);
        TreeNode node6=new TreeNode(5);
        TreeNode node10=new TreeNode(12);
        TreeNode node5=new TreeNode(4);
        TreeNode node7=new TreeNode(7);
        TreeNode node9=new TreeNode(9);
        TreeNode node11=new TreeNode(11);
        node6.left=node5;
        node6.right=node7;
//        node10.left=node9;
//        node10.right=node11;
        root.left=node6;
        root.right=node10;

        Test06 test06 = new Test06();
        ArrayList<ArrayList<Integer>> arrayLists = test06.FindPath(root, 22);

        for(ArrayList<Integer> list:arrayLists){
            System.out.println(list);
        }
    }
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {

        ArrayList<ArrayList<Integer>> result=new ArrayList<>();
        if(root==null){
            return result;
        }
        diGui(root,expectNumber,result,0,"");
        return result;
    }
    public void diGui(TreeNode node, int sum, ArrayList<ArrayList<Integer>> result,int value,String str){
        value=value+ node.val;
        str+=node.val+",";

        // 这是叶子节点
        if(node.left==null&&node.right==null){
            if(sum==value){
                String[] split = str.split(",");
                ArrayList<Integer> list=new ArrayList<>();
                for(String s:split){
                    if(s!=null&&!"".equals(s)){
                        list.add(Integer.parseInt(s));
                    }
                }
                result.add(list);
            }
        }
        if(node.left!=null) {
            diGui(node.left, sum, result, value, str);
        }
        if(node.right!=null) {
            diGui(node.right, sum, result, value, str);
        }
    }
}
